package 剑指offer;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 17:34 星期三
 */
public class _21_调整数组顺序使奇数位于偶数前面 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4};
        System.err.println(Arrays.toString(exchange(nums)));
    }

    /**
     * 双指针，性能有点差
     * > 2022/08/24 17:41:34
     * 解答成功:
     * 	执行耗时:2 ms,击败了40.86% 的Java用户
     * 	内存消耗:49.1 MB,击败了78.65% 的Java用户
     * @param nums
     * @return
     */
    public static int[] exchange(int[] nums) {
        //定义双指针lp和rp
        int lp = 0, rp = nums.length - 1;
        //若lp<rp恒成立，循环继续
        while (lp < rp) {
            if (nums[lp] % 2 == 0) {
                //左指针遇到偶数，所以左指针不动
                if (nums[rp] % 2 == 1) {
                    //右指针遇到奇数，二者交换
                    exch(nums, lp, rp);
                    //左指针此时可以右移
                    lp++;
                }
                //右指针此时可以左移
                rp--;
            }else{
                //左指针没有遇到不符合条件的，右移
                lp++;
            }
        }
        return nums;
    }

    public static void exch(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}
